The present invention relates to architectures for fast information retrieval and, more particularly, to the design of architectures for packet classification.
Multi-dimensional search problems such as packet classification pose a number of challenges. Packet classifiers, for example, typically consist of a set of rules that are applied to an incoming packet-where each packet must be classified based on several different fields in the packet header, e.g., source and destination address, protocol, port, etc. Packet classification in its fullest generality has been shown to require exponential complexity in either time or space. Hence, current efforts use heuristics in an effort to provide a feasible solution in practical real-world situations. The favored commercial solution for packet classification is the ternary content-addressable memory (TCAM). TCAMs are specialized memories that simultaneously compare a query with all stored entries and have guaranteed constant search latencies. While TCAMs have advantages over other existing hardware and software solutions, TCAMs are expensive and do have scalability issues: as classifiers grow in size, their power dissipation becomes prohibitive and their performance can degrade, i.e., the latency of a search, while deterministic and independent of classifier properties, can increase.
Accordingly, there is a need for an improved information retrieval architecture for handling such multi-dimensional search problems.